import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set=new HashSet<>(wordList);
        if(!set.contains(endWord)) return 0;

        int count=0;

        Queue<String> q=new LinkedList<>();
        q.add(beginWord);


        while(!q.isEmpty()){

            int sz=q.size();

            for(int i=0;i<sz;i++){
                String cur=q.poll();
                if(cur.equals(endWord)) return count+1;
                char[] scur=cur.toCharArray();
                for(int k=0;k<scur.length;k++){
                    char or=scur[k];

                    for(char c='a';c<='z';c++){
                        if(scur[k]==c) continue;
                        scur[k]=c;
                        String strcur=new String(scur);

                        if(set.contains(strcur)){
                            q.add(strcur);
                            set.remove(strcur);

                        }
                            scur[k]=or;

                    }
                }
            }
            count++;
        }
        return 0;



    }
}



class Solution12 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) return -1;

        char[] genes = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        int mutations = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                String current = queue.poll();
                if (current.equals(endGene)) return mutations;

                char[] currentGenes = current.toCharArray();
                for (int i = 0; i < currentGenes.length; i++) {
                    char original = currentGenes[i];
                    for (char gene : genes) {
                        if (gene == original) continue;
                        currentGenes[i] = gene;
                        String nextGene = new String(currentGenes);
                        if (bankSet.contains(nextGene)) {
                            queue.add(nextGene);
                            bankSet.remove(nextGene);  // 避免重复添加
                        }
                    }
                    currentGenes[i] = original;  // 恢复原状态
                }
            }
            mutations++;
        }
        return -1;
    }
}

class Solution1 {
    int[] dx={0,0,-1,1};
    int[] dy={1,-1,0,0};
    int m,n;
    int[][] ret;
    public int[][] updateMatrix(int[][] mat) {
        m=mat.length;
        n=mat[0].length;
        ret=new int[m][n];
        Queue<int[]> q=new LinkedList<>();
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(mat[i][j]==0) q.add(new int[]{i,j});
                else ret[i][j]=-1;
            }

        bfs(mat,q);



        return ret;





    }


    public void bfs(int[][] mat,Queue<int[]> q){

        while(!q.isEmpty()){


            int[] arr=q.poll();
            int x=arr[0];
            int y=arr[1];
            for(int k=0;k<4;k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&ret[nx][ny]==-1){
                    q.add(new int[]{nx,ny});
                    ret[nx][ny]=ret[x][y]+1;
                }
            }



        }
    }




}